#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <vector>

using namespace std;

class Node {
   public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> getListNode(Node* t) {
    vector<int> tmp;
    while (t) {
        tmp.push_back(t->val);
        t = t->next;
    }
    return tmp;
}

class Solution {
   public:
    Node* copyRandomList(Node* head) {
        Node *tmp = head, *tmp2 = head, *tmp3 = head, *tmp4 = head;
        while (tmp != NULL) {
            Node* new_node = (Node*)malloc(sizeof(Node));
            new_node->val = tmp->val;
            new_node->next = tmp->next;
            tmp->next = new_node;  //拼接
            tmp = tmp->next->next;
        }
        while (tmp2 != NULL) {
            if (tmp2->random != NULL) {
                tmp2->next->random = tmp2->random->next;
            }
            tmp2 = tmp2->next->next;
        }
        tmp3 = tmp3->next;
        tmp4 = tmp3;
        while (tmp3->next != NULL) {
            tmp3->next = tmp3->next->next;
            tmp3 = tmp3->next;
        }
        return tmp4;
    }
};

int main() {
    cout << "Hello, World!";
    Node node1 = Node(0), node2 = Node(1), node3 = Node(2);
    node1.next = &node2;
    node2.next = &node3;
    node2.random = &node1;
    Solution().copyRandomList(&node1);
    return 0;
}